package ltd.newson.easy;

import java.util.HashMap;
import java.util.Map;

public class EASY_1160_拼写单词 {
    /**
     * 题目条件：对于每个单词，每个字母只能使用一次。
     * @param args
     */
    public static void main(String[] args) {
        EASY_1160_拼写单词 clazz = new EASY_1160_拼写单词();
        /**
         * 输入：words = ["cat","bt","hat","tree"], chars = "atach"
         * 输出：6
         * 解释：
         * 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
         */
        String[] words = new String[] {"cat","bt","hat","tree"};
        String chars = "atach";
        System.out.println(clazz.countCharacters(words, chars));

    }


    /**
     * 解题思路：理解题意，是每个单词只能使用一次字母表中的字母，所以对每个单词而言，字母表都是完整的。
     * 只需要对字母表hash，分别对比每一个单词，只要字母表的字母数量大于等于但前单词即可加上当前单词长度。
     * @param words
     * @param chars
     * @return
     */
    public int countCharacters(String[] words, String chars) {
        Map<Character, Integer> resources = new HashMap<Character, Integer>(16);
        int len = chars.length();
        int ans = 0;
        for (int i = 0; i < len; ++i) {
            char c = chars.charAt(i);
            resources.put(c, resources.getOrDefault(c, 0) + 1);
        }
        for (String word : words) {
            Map<Character, Integer> targetMap = new HashMap<Character, Integer>(16);
            int strLen = word.length();
            for (int i = 0; i < strLen; ++i) {
                char c = word.charAt(i);
                targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
            }
            boolean isAns = true;
            for (int i = 0; i < strLen; ++i) {
                char c = word.charAt(i);
                if (targetMap.getOrDefault(c, 0) > resources.getOrDefault(c, 0)) {
                    isAns = false;
                    break;
                }
            }
            if (isAns) {
                ans += word.length();
            }
        }
        return ans;
    }
}
